package com.zk.algorithm.others;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.Stack;

/**
 * 有效的括号对 栈
 *
 * @author zk
 */
@Easy
@LeetCodeExplore
public class ValidParentheses {

    public boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }

        Stack<Character> stack = new Stack<>();
        int i = 0;

        while (i < s.length()) {
            char c = s.charAt(i);

            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                switch (c) {
                    case ')':
                        if (!expected(stack, '('))
                            return false;
                        break;

                    case ']':
                        if (!expected(stack, '['))
                            return false;
                        break;

                    case '}':
                        if (!expected(stack, '{'))
                            return false;
                        break;
                }
            }

            i++;
        }

        // 返回栈是否为空
        return stack.isEmpty();
    }

    private boolean expected(Stack<Character> stack, char expected) {
        if (stack.isEmpty()) {
            return false;
        }

        return stack.pop().charValue() == expected;
    }

    public static void main(String...args) {
        Utils.println(new ValidParentheses().isValid("{[]}"));
        Utils.println(new ValidParentheses().isValid("([)]"));
    }

}
